1. Field of the Invention
The present invention relates to a divider carrying out division of binary numbers by means of hardware.
2. Description of Related Art
Division is achieved by sequential processing algorithm which iterates multiplication and decision of a result. Although various special hardware systems are proposed for shrinking processing time, they still demand much greater time than multiplication or addition, and hence a faster divider is desired. We will explain division algorithm below, in which X designates a dividend, Y designates a divisor, R.sup.i designates an i-th partial remainder, Q designates a quotient, q.sub.i designates an i-th digit of the quotient, Z designates a quotient converted into a binary number, and r.sup.i 1, r.sup.i 0, and r.sup.i -1 designates upper three bits of the i-th partial remainder R.sup.i. ##EQU1##
First, at step 1, the dividend X and the divisor Y are input which are normalized such that 1.ltoreq.X&lt;2 and 1.ltoreq.Y&lt;2. At step 2, the partial remainder R.sup.1 represented in a redundant binary number is obtained by setting to one the most significant digit q.sub.0 of the quotient Q. The partial remainder R.sup.1 can be obtained by subtracting the divisor Y from the dividend X. Since both the dividend X and divisor Y are a binary number here, the partial remainder R.sup.1 represented in the redundant binary number can be obtained by subtraction of respective digits without a carry. At step 3, upper three bits r.sup.i 1 r.sup.i 0. r.sup.i -1! of the generated partial remainder R.sup.i undergo successive decision whether they are negative, zero or positive for i=1, 2, . . . , n, so that the quotient q.sub.i is obtained by the number of digits required. Finally, at step 4, the quotient Q represented in the redundant binary number is converted into the quotient Z represented in the binary number, thus ending the processing.
FIG. 15 is a block diagram showing the divisor in its entirety using the redundant binary representation based on the foregoing division algorithm, which is disclosed, for example, in "A VLSI-Oriented High-Speed Divider Using Redundant Binary Representation", by Naofumi TAKAGI, Hiroto YASUURA, and Shuzo YAJIMA, The Journal D of the Institute of Electronics, Information and Communication Engineers of Japan, 84/4, Vol.J67-D, No. 4, pp.450-457. The divider is implemented by employing ECL (Emitter Coupled Logic) as its internal circuit. In FIG. 15, a double square designates a cell for deciding a quotient, and a single square designates a cell for carrying out redundant binary addition and subtraction. Each row of cells designated by the single squares forms a redundant binary adder and subtractor for the redundant binary addition and subtraction, and each row of cells consisting of the redundant binary adder and subtractor plus the single cell for making quotient decision designated by the double square carries out computation for one loop of step 3 in the foregoing division algorithm.
FIGS. 16 and 17 are block diagrams showing a quotient decision circuit and partial remainder generation and addition circuit constituting the divider using the redundant binary representation based on the foregoing division algorithm, which is disclosed, for example, in "High-Speed Multiplier and Divider using Redundant Binary Representation", by Takashi TANIGUCHI, Hisakazu EDAMATSU, Tamotsu NISHIYAMA, Shigeo KUNINOBU and Naofumi TAKAGI, Technical Research Report ED88-48 of the Institute of Electronics, Information and Communication Engineers of Japan. The quotient decision circuit and the partial remainder generation and addition circuit are implemented using a CMOS (Complementary Metal-Oxide Semiconductor) circuit.
The quotient decision circuit as shown in FIG. 16 makes a decision of the quotient q.sub.i from the upper three bits of the partial remainder R.sup.i as shown in step 3 of the foregoing division algorithm. The redundant binary representation of the upper three bits of the partial remainder R.sup.i and the quotient q.sub.i represents (1, 0, -1) by (10, 00, 01) using a pair of signals {z.sub.ip, z.sub.in }, so that the decision is easily made whether the value is positive or negative. This simplifies the configuration of the quotient decision circuit.
The partial remainder generation and addition circuit as shown in FIG. 17 is used for computing the partial remainder R.sup.i+1 at step 3 of the foregoing division algorithm. It is necessary for the generation of the partial remainder R.sup.i+1 at step 3 to subtract the product of the quotient q.sub.i and the divisor D from the partial remainder consisting of a redundant binary number which is shifted to the left by one digit. However, since the divisor D is a binary number, it is only necessary to consider computation between the redundant binary number and the binary number. Thus, the adder is arranged such that it adds the divisor D when the i-th digit q.sub.i of the quotient Q is -1, adds zero when q.sub.i is zero, and adds the two's complement of the divisor D when q.sub.i is one. In this way, only the addition of the redundant binary number and the binary number is required, which simplifies the configuration of the partial remainder generation and addition circuit because the carry is always non-negative. The partial remainder generation and addition circuit, however, uses a redundant binary representation different from that of the quotient decision circuit, where (1, 0, -1) is represented as (11, 10, 01) using a pair of signals {z.sub.is, z.sub.ia }.
Arraying the quotient decision circuits and the partial remainder generation and addition circuits thus arranged makes it possible to construct a divider with a regular cell arrangement, in which the quotient decision circuits as shown in FIG. 16 are placed as the quotient decision cells designated by the double squares in FIG. 15, and the partial remainder generation and addition circuits as shown in FIG. 17 are placed as the redundant binary addition and subtraction circuits designated by the single squares. The conversion of the quotient into a binary number by a redundant binary-to-binary converter can be carried out by subtracting the binary number consisting of q.sub.iN from the binary number consisting of q.sub.iP, which are output from the respective quotient decision circuits.
Thus, the conventional divider uses different redundant binary representations in the quotient decision circuit as shown in FIG. 16 and the partial remainder generation and addition circuit as shown in FIG. 17. Accordingly, it is necessary to unify the redundant binary representations by inserting a converter between the two circuits.
FIG. 18 is a block diagram showing an example of such a converter which converts a redundant binary number in which (1, 0, -1) is represented by (11, 10, 01) into a redundant binary number in which (1, 0, -1) is represented by (10, 00, 01). More specifically, when (1, 1) representing +1 is input as z.sub.is and z.sub.ia, it is converted into z.sub.ip and z.sub.in of (1, 0), and its inverted signal (0, 1) is output. Likewise, when (1, 0) representing zero is input, it is converted to (0, 0) and its inverted signal (1, 1) is output, and when (0, 1) representing -1 is input, it is converted to (0, 1) and its inverted signal (1, 0) is output.
FIG. 19 is a block diagram showing a quotient decision circuit, to which such converters are added to its input. The upper three bits r.sup.i 1 r.sup.i 2 r.sup.i -1! of the partial remainder R.sup.i generated by the respective partial remainder generator and addition circuits are converted by the converters from the redundant binary number in which (1, 0, -1) is represented as (11, 10, 01) to the redundant binary number in which (1, 0, -1) is represented as (10, 00, 01).
In the conventional divider with such a configuration, the conversion is needed before making a quotient decision because the subtraction cells (partial remainder generator and addition circuits) for computing the partial remainders and the quotient decision cells for making the quotient decision (quotient decision circuits) use different redundant binary representations. This presents a problem in that the converter is essential, which complicates the configuration of the divider, and hinders the processing time of the division from being reduced owing to the delay of the conversion.